1 I B HAHY OF THE U N IVERSITY Of ILLINOIS 510,84 I^6r no. 156-163 c o p 2 r ^ATHEMP • DIGITAL COMPUTER LABORATORY UNIVERSITY OF ILLINOIS URBANA, ILLINOIS REPORT NO, 162 MINIMAL THREE-VARIABLE "NOR" AND "NAND" LOGIC CIRCUITS by Robert Allan Smith May 15, 196k (This work is being submitted in partial fulfillment of the requirements for the Degree of Master of Science. ) MTHEMA1 LIBRARY Digitized by the Internet Archive in 2013 http://archive.org/details/minimalthreevari162smit ACKNOWLEDGMENT The author wishes to express his sincere thanks to Professor To A, Murrell, his thesis advisor, for assistance in the preparation of this thesis. Return this book on or before the Latest Date stamped below. Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University. University of Illinois Library MAR B W87 L161— O-1096 TABLE OF CONTENTS Page 1. INTRODUCTION 1 2. DESCRIPTION OF THE PROGRAM 3 2.1 The Universal Circuit 3 2.2 Generation of Matrices k 2.3 Processing of Matrices 5 3. COMMENTS ON THE RESULTS .......... 6 k. TABLE OF RESULTS ................. 7 5. CIRCUIT DIAGRAMS . 18 6. CONCLUSIONS ...... 20 BIBLIOGRAPHY .... ................ 21 -in MINIMAL THREE-VARIABLE "NOR" AND "NANIj" LOGIC CJ Robert Allan Smith, M.S. Department of Electrical Engineering University of Illinois, 196^ This paper presents a table of minimal NOR and NAND combinational circuits for the 256 logical functions of three variables, assuming complemented inputs are available. The circuits were found by an exhaustive method, using a computer. The criteria used for minimality were, first, minimality with respect to the number of logic elements, and second, minimality with respect to the total number of inputs to all elements, subject to the first condition. The results show that all 256 functions can be generated using five or fewer NOR or NAND elements. ■IV- 1. INTRODUCTION Circuits composed of NOR or NAND elements, while not the fastest type of circuits, are used extensively, mainly because of their economy--one type of element may be used throughout an entire circuit. Assuming the basic decision to use such "universal" elements has been made, the main design objective will usually be to produce either the fastest or the most economical circuit possible. The fastest NAND circuits, i.e., minimum levels, are obtained by rewriting the minimum-OR polynomial (as obtained by the Quine-McCluskey method) in terms of the NAND connective, yielding a three-level logic (two-level if complemented inputs are available). Similarly the minimum- AND polynomial may be written in terms of the NOR connective. Circuits obtained in this way are often also mini- mal with respect to the number of logic elements required. At present there are no known algebraic methods of obtaining absolutely minimal NOR or NAND circuits, or for that matter, circuits using any other types of logic elements. Methods such as the Quine-McCluskey method and the Karnaugh 1 3 map method ' give only near-to-minimal realizations. Recently, however, 2 Hellerman has reported the results of an exhaustive method utilizing a computer. The criteria used for minimality were, first, minimality with respect to the number of logic elements, and second, minimality with respect to the total number of inputs to all elements, subject to the first condition. Complemented inputs were assumed not available. In Hellerman ' s approach, a universal circuit configuration was set up which permitted systematic investigation of all the possible ways of connecting together a given number of NOR elements . The program began by generating as many functions as possible using one NOR element and storing the circuit configuration and the number of inputs required, in memory. Then, all possible configurations of two NOR elements were considered. If a particular function had been generated -1- previously with fewer elements or with the same number of elements but with fewer inputs, the configuration under consideration was discarded. If the func- tion had been generated previously with the same number of elements but with more inputs, the information regarding the configuration and the number of inputs replaced the previously stored information for that function. The program con- tinued in this way, up to seven NOR elements, and yielded a catalog of minimal NOR realizations for the 256 logical functions of three variables. Minimal NAND realizations were derived from the set of NOR realizations. The results reported in this thesis form an extension of Hellerman's work. A similar catalog is given, with the difference being that complemented inputs are assumed available. The same minimality criteria are used. The results show that with complemented inputs, all 256 functions can be generated using five or fewer NOR or NAND elements. 2. DESCRIPTION OF THE PROGRAM The computer program was written in the assembler language SCATRE and was run on the IBM 709^+, the total running time being approximately 35 minutes. The program considered NAND circuits rather than NOR circuits, and began with one NAND element, continuing up to four NAND elements, 2.1 The Universal Circuit The universal circuit which allowed investigation of all possible configurations of four NAND elements is shown in Fig„ 1. Inputs a b c a b c 123^56 7 89 FIGURE 1. THE UNIVERSAL CIRCUIT Output Crossover points are either connected or disconnected, indicating which inputs feed the various elements. The circuit is then representable by a connec- tion matrix, a matrix of ones and zeros, each element of which indicates the presence or absence of a connection at the corresponding point in the circuit „ A separate computer word was used to represent each row of the matrix. Since 30 ^ 9 each connection point has two possible values, there are 2 ~ 10 possible -3- connection matrices. Many of these will, however, result in useless circui' and there are a number of restrictions which may be placed on the form of the connection matrix to eliminate these. Some restrictions are difficult to incor- porate into a program and some effect only a small saving of time. The following three restrictions were used in the final program: 1. An input and its complement (e.g. , a and a) were not allowed to be fed into the same NAND element. 2. Columns 1, 2, and 3 were "ordered," i.e., if A, B, and C represent the values of columns 1, 2, and 3 when considered as binary numbers, then it was required that A > B > C This means that the program investigated only one member from each of the 80 equivalence classes of functions of three variables, i.e., one member from each set of con- nection matrices whose members differ only in that they effect a permutation of input variables. 3. Each element in the circuit had to be "useful," i.e., the output of every element (except the last) had to feed some other element. The number of matrices connecting four NAND elements which will pass the above restrictions is approximately 5 X 10 > a considerable saving over the original number. 2.2 Generation of Matrices The systematic generation of matrices connecting four NANB elements was carried out as follows. Because of restriction 3j there are only 21 possible partial matrices consisting of columns 7, 8, and 9° These were stored in memory to be added to the remaining portion of the matrix. Because of restriction 1, there are only 27 permissible ways of "filling" the portion of any row up to column 6. These were similarly stored in 27 words. An outer program loop selected one of the 21 partial matrices for columns 7> 8, and 9- Inner loops systematically selected partial rows from the 27 possible ones, such that all combinations were exhausted. After generation of a particular matrix, columns 1, 2, and 3 were checked for ordering. If ordering was present the matrix was "processed" to determine what logical function it produced; if not, a new matrix was generated. 2.3 Processing of Matrices The processing of a given matrix was the key portion of the program since it was repeated so many times; hence it had to be made as economical as possible. The basic method of processing was the same as used by Hellerman, i.e., the output of the circuit was determined for each of the eight possible input combinations. The sequence of machine instructions used to accomplish this was different however, and is thought to be as efficient as possible, A given input combination was placed in the sense-indicator (Si) register. Then each bit position of the word for row 1 which was a one was compared with the corresponding bit in the SI register, using the ONT (on-test for indicators) instruction. If all corresponding positions were also one this meant that the output of the NAND element in row 1 was zero, and the computer skipped the next instruction. If any position was zero, this meant that the output of the NAND element was a one, and the machine executed the next instruction, which placed (via the OSI instruction) an additional one in the "column-7" position of the SI reigster. This process was then repeated for the remaining rows. 3. COMMENTS ON THE RESULTS Not all of the 256 functions of three variables were generated by the circuits containing up to four NAND elements. Circuits for the ten remaining functions were found and are included in the table of results. They all contain five NAND elements and hence are minimal with respect to the number of elements, but they may not be minimal with respect to the number of inputs. The set of minimal NOR circuits is also given in Table 1. These were obtained directly from the minimal NAND circuits using the fact that any minimal NAND circuit realizing a function F(a,b,c) will also represent a minimal NOR circuit for the function G(a,b,c) where F(a,b,c) = G(a,b,c) -6- h, TABLE OK RESULTS Table 1 lists the minimal NOR and NAND realizations for the 256 functions of three variables, assuming complemented inputs are available. The functions are listed according to an octal number which indicates which minterms are present in the canonical expansion of the function, Writing a given octal designation number as an 8-bit binary number (filling in left zeros if necessary), the bits, from left to right, indicate the presence or absence of the terms abc, abc, abc, abc, abc, abc, abc, abc. The circuit numbers and the corresponding inputs refer to the circuit diagrams following the table. A circuit number of zero indicates that the function requires no NAND element--it is either just a single literal or iden- tically zero or one. Several functions have two minimal realizations. In such cases the alternative realization is listed immediately following the main entry. -7- TABLE 1. Fen. NAND Inputs NOR Inputs No. Expression Cct. l 2 3 k 5 6789 Cct. 1 2 3 k 5 6 7 8 9 1 abc 3 a b c 2 a b c 2 abc 3 a b c 2 a b c 3 ab k a b 1 a b k abc 3 a b c 2 a b c 5 ac k a c 1 a c 6 a(bc+bc) 7 a b c a b c 10 b c b c a 7 a(b+c) 6 b c a 5 b c a 10 abc 3 a b c 2 a b c 11 a(bc+bc) 7 a b c a b c 10 c b b c a 12 ac k a c 1 a c 13 a(b+c) 6 b c a 5 c b a Ik ab k a b 1 a b 15 a(b+c) 6 c b a 5 b c a 16 a(b+c) 6 b c a 5 b c a IT a a a 20 abc 3 a b c 2 a b c 21 be k b c 1 b c 22 b(ac+ac) 7 b c a b c a 10 a c a c b 23 b(a+c) 6 c a b 5 a c b 24 c ( ab+ab ) 7 c a b c a b 10 a b a b c 25 c ( a+b ) 6 a b c 5 a b c 26 abc+abc+abc 11 a b c a b c a b c 18 a b a c b c a b c 27 ab+ac+bc 12 b c a b c 12 b c a b c 30 abc+abc 7 a b c a b c 15 16 b b c a a c b a c a b c 31 abc+bc 8 b c a b c Ik 12 b a c c a b b b c c 32 ac+abc 8 a c a b c < Ik 12 a b c c b a a a c c 33 ac+bc 9 b c a c 9 a c b c TABLE 1 (CONT'D). Fcn< No. Expression NAND Inputs N ffl Cct. 12 3 4 5 6 7 8 9 Cct, Inputs 123456789 34 45 kG ab+abc 35 ab+bc 36 a(b+c)+abc 37 a+bc l+O abc l+l b(ac+ac) 1+2 be 43 b(a+c) kk abc+abc abc+ac bc+abc hi bc+ac 50 abc+abc 51 abc+abc+abc 52 c ( a+b ) 53 c(a+b)+ab 54 ab+abc 55 a(b+c)+abc 56 ab+bc 57 a+bc 60 ab 61 b(a+c) 62 b(a+c) 63 b 61+ ab+abc a b a b c 9 a b c b 13 b c a b c a 5 b c a 3 b c a 7 b c a b c a 1+ b c 6 a c b 7 b c a b c a 65 ab+ac 8 c a b c a 8 b c a b c 9 b c a c 7 a b c a b c 11 abcabcabc 6 abc 12 a b c a b 8 a b a b c 13 b c a b a c 9 abbe 5 b c a 1+ a b 6 a c b 6 cab b 8 a b a b c 9 abac 11+ 12 9 13 6 2 10 1 5 15 16 ll+ 12 11+ 12 9 10 18 5 12 11+ 12 13 9 6 1 5 5 ik 12 9 a b c b b c b c b c c a c a c b c a c a c b c a b a b c a c b c a b a b a b b c a b b c b c a b c b a b a c a c b b a c a a b cab a a b b a a b c a a b cab b b c a b a b c a b c a c c a abc b b c a c abc a c b c a b c c abc a c b a a b abac b c a b b c b a b b a a c TABLE 1 (CONT'D). 10 Fen, No, Expression NAND Inputs NOR Cct. 12 3 4 5 6 7 8 9 Cct, Inputs 123456789 66 b(a+c)+abc 67 b+ac 70 ab+ab c 71 b(a+c)+abc 72 ab+ac 73 b+ac 74 ab+ab 75 ab+ab+ac 13 c a b c a b 15 cab 8 a b a b c 13 c a b cab 6 a c b 1J+ b a b c a 12 a c b b a 13 a c b a b c 9 a b a c 6 a c b 9 a b a b 8 a b c a b 76 ab+ab+ac a b a b c 77 a+b 100 abc 101 c( ab+ab) 102 abc+abc 103 abc+ab 104 be 105 c ( a+b ) 106 bc+abc 107 bc+ab 110 abc+abc 111 abc+abc+abc 112 ac+abc 113 a(b+c)+abc 114 b ( a+c ) 115 b(a+c)+ac 116 ac+bc 1 a b 4 a b 3 a b c 2 a b c 7 c a b c a b 10 a b a b c 7 a b c a b c 15 a b c a b c 16 a c b c a b 8 a b c a b 14 12 a c b b c a a a b b 4 b c 1 b c 6 a b c 5 b a c 8 b c a b c 14 12 c a b b a c c c b b 9 b c a b 9 b a b c 7 a b c 8 b c 10 a c a c b 11 a b c a b c a b c 18 a b a c b c a b c 8 a c a b c 14 12 a c c b a a b a c c 13 c b a c a b , !3 c b a c a b 6 c a b 5 c a b 12 c a b c a 12 a b c a b 9 a c b c 9 b c a c TABLE 1 (CONT'D). Fen. NAND Inputs NOR Inputs No. Expression Cct. 1 2 3 4 5 6 7 8 9 Cct. 1 2 3 4 5 6 7 8 9 117 a+bc 5 c b 8 6 b c a 120 ac 4 a c 1 a c 121 c ( a+b ) 6 b a C 5 a b c 122 ac+abc 8 a c a b c 14 12 c b a a b c c c a a 123 ac+ab 9 a c a b 9 a b a c 124 c ( a+b ) 6 a b c 5 a b c 125 c c c 126 c(a+b)+abc 13 a b c a b c 13 a b c a b c 127 c+ab 5 a b c 6 a b c 130 ac+abc 8 a c a b c 14 12 c a a b c c b c a a 131 c(a+b)+abc 13 a b c a c b 13 a b c a c b 132 ac+ac 9 a c a c 9 a c a c 133 ac+ac+bc 14 12 c c a b c a a c b a 8 a c a b c 134 ac+ab 9 a c a b 9 a b a c 135 c+ab 5 a b c 6 b a c 136 ac+ac+bc 14 12 c b a c b a c c a a 8 a c a b c 137 a+c 1 a c 4 a c 140 abc+abc 7 a b c a b c 10 b c b c a i4i abc+abc+abc 11 a b c a b c a b c 18 a c b c a b a b c ite bc+abc 8 b c a b c 14 12 b c c a b b a b c c U3 b(a+c)+abc 13 c a b c b a 13 c a b c b a 144 bc+abc 8 b c a b c 14 12 c b b a c c a c b b 145 c(a+b)+abc 13 b a c b c a 13 b a c b c a 146 bc+bc 9 b c b c 9 b c b c 147 bc+bc+ab 14 12 b b c a b c c b a c 8 b c a b c UNIVERSITY Of TABLE 1 (CONT'D) . Fen, NAND Inputs NOR Inputs No. Expression Oct. 1 2 3 k 5 6 7 8 9 Cct. 1 2 3 k 5 6 7 89 150 abc+abc+abc 11 a b c a 5 c a b c 18 a b a c b c a b c 151 c ( ab+ab ) +c ( ab+ab ) 17 a b c b c a 17 a b c b c a 152 c(a+b)+abc 13 a b c c a b 13 a b c c a b 153 ac+ab+bc+abc 18 a c a b b c a b c 11 a b c a b c a b c 15^ b(a+c)+abc 13 c a b b c a 13 c a b b c a 155 a(b+c)+bc+abc 18 b c a c a b a b c 11 a b c a b c a b c 156 a(b+c)+bc+bc 11+ 12 b c c a b b c b a c 8 b c a b c 157 a+bc+bc 10 b c b c a 7 b c a b c a 160 a(b+c) 6 b c a 5 b c a 161 a(b+c)+bc 12 b c a b c 12 c a b c a 162 bc+ca 9 b c c a 9 a c b c 163 b+ac 5 c a b 6 a c b 164 bc+ab 9 c b b a 9 a b b c 165 c+ab 5 b a c 6 a b c 166 bc+bc+ab Ik 12 b a c b a c b b c c 8 b c a b c 167 b+c 1 b c k b c 170 a(b+c)+abc 13 b c a a b c 13 b c a a b c 171 a(b+c)+abc+bc 18 a b a c b c a b c 11 a b c a b c a b c 172 b(a+c)+ac+ac Ik 12 c a a b c c a c b a 8 c a c a b 173 b+ac+ac 10 c a c a b 7 c a b c a b 17^ c ( a+b ) +ab+ab Ik 12 a b b c a a b a c b 8 a b a b c 175 c+ab+ab 10 a b a b c 7 a b c 8. b c 176 ab+bc+ac 15 16 a b b c c a a b b a c c 7 a b c a b c 177 a+b+c 2 a b c - 3 a b c 200 abc 3 a b c 2 a b c 201 abc+abc 7 a b c a b c 15 16 a b b c c a a b b a c c TABLE 1 (CONT'D). Fen. NAND Inputs NOR Inputs No. Expression Cct. 1 2 3 1+ 5 6 7 8 9 Cct, 1 2 3 1+ 5 6 7 8 9 202 c ( ab+ab ) 7 a b c a b c 10 a : a b c 203 abc+ab 8 a b a b c 11+ 12 a b b c a a b a c b 201+ b(ac+ac) 7 c a b c a b 10 c a c a b 205 abc+ac 8 c a c a b 11+ 12 c a a b c c a c b a 206 abc+abc+abc 11 a b c a b c a b c 18 a b a c b c a b c 207 abc+a(b+c) 13 b c a a b c 13 b c a a b c 210 be 1+ b c 1 b c 211 abc+bc 8 b c a b c 11+ 12 b a c b a c b b c c 212 c ( a+b ) 6 a b c 5 b a c 213 ab+bc 9 a b b c 9 c b b a 211+ b(a+c) 6 a c b 5 c a b 215 ac+bc 9 a c b c 9 b c c a 216 ab+ac+bc 12 c a b c a 12 b c a b c 217 a+bc 5 b c a 6 b c a 220 a(bc+bc) 7 b c a b c a 10 b c b c a 221 abc+bc 8 b c a b c 11+ 12 b c c a b b c b a c 222 abc+abc+abc 11 a b c a b c a b c 18 b c a c a b a b c 223 abc+b(a+c) 13 c a b b c a 13 c a b b c a 221+ abc+abc+abc 11 a b c a b c a b c 18 a c a b b c a b c 225 abc+c(a+b) 13 a b c c a b 13 a b c c a b 226 ab c +ab c +ab c +ab c 17 a b c b c a 17 a b c b c a 227 ab+ac+bc+abc 18 a b a c b c a b c 11 a b c a b c a b c 230 abc+bc 8 b c a b c 11+ 12 b b c a b c c b a c 231 bc+bc 9 b c b c . 9 b c b c 232 c(a+b)+abc 13 b a c b c a 13 b a c b c a 233 bc+b(a+c) Ik 12 c b b a c c a c b b 8 b c a b c TABLE 1 (CONT'D). Fen. No. Expression NAND Cct. 1 2 3 Inputs 456789 NOR Cct. 1 2 3 Inputs 4 5 6 7 8 9 234 b(a+c)+abc 13 c a b c b a 13 c a b c b a 235 bc+c(a+b) 14 12 b c c a b b a b c c 8 b c a b c 236 c(a+b)+ab+abc 18 a c b c a babe 11 a b c a b c a b c 237 a+bc+bc 10 b c b c a 7 a b c a b c 240 ac 4 a c 1 a c 241 ac+abc 8 a c a b c 14 12 c b a c b a c c a a 242 c ( a+b ) 6 b a c 5 a b c 243 ab+ac 9 a b a c 9 a c a b 244 ac+abc 8 a c a b c 14 12 c c a b c a a c b a 245 ac+ac 9 a c a c 9 a c a c 246 c(b+a)+abc 13 a b c a c b 13 a b c a c b 247 ac+a(b+c) 14 12 c a a b c c b c a a 8 a c a b c 250 c ( a+b ) 6 a b c 5 a b c 251 c(a+b)+abc 13 a b c a b c 13 a b c a b c 252 c c c 253 ab+c 5 a b c 6 a b c 254 ab+ac 9 a b a c 9 a c a b 255 ac+bc+ac 14 12 c b a a b c c c a a 8 a c a b c 256 ab+c 5 a b c 6 b a c 257 a+c l a c 4 a c 260 a(b+c) 6 b c a 5 c b a 261 bc+ac 9 b c a c 9 a c b c 262 bc+ab+ac 12 a b c a b 12 c a b c a 263 b+ac 5 c a b 6 c a b 264 a(b+c)+abc 13 c b a c a b 13 c b a c a b 265 ac+c(a+b) 14 12 a c c b a a b a c c 8 a c a b c 266 a(b+c)+bc+abc 18 a b a c b c a b c 11 a b c a b c a b c TABLE 1 (CONT'D). Fen. No. Expression 267 ac+ac+b 270 ab+bc 271 bc+ac+bc 272 ab+c 273 b+c 27^ a(b+c)+ab NAND Inputs NOR Cct. 12 3^56789 Cct. Inputs 123^56789 275 a(b+c)+a(b+c) 276 ab+ab+c 277 a+b+c 300 ab 301 ab+abc 302 ab+abc 303 ab+ab 30^ b(a+c) 305 ab+ac 306 b(a+c)+abc 307 ab+a(b+c) 310 b(a+c) 311 b(a+c)+abc 312 ab+ac 313 ab+ab +bc 31k b 315 ac+b 316 ac+b 317 a+b 320 a(b+c) 10 a c a c b 9 b a b c Ik c b a c b 12 a b c c b 5 b a c 1 b c Ik a b c a b 12 c b a a b 15 a b c a b c 16 a c b c a b 10 a b a b c 2 a b c k a b 8 a b a b c a b c a b 9 a b a b 6 a c b 9 a b a c 13 a c b a b c ll+ b a b c a 12 a c b b a 6 a c b 13 c a b c a b 9 a b a c Ik b a c b a 12 c a b b a b 5 a c b 5 a c b 1 a b 6 c b a 7 a b cab c 9 b c a b 8 b c a b c 6 a b c k b c 8 a b cab a b c a b c 7 c a b c a b 3 a b c 1 a b Hi a b c a b 12 c a b a b Ik a b a b c 12 a c b a b 9 a b a b 5 a c b 9 a b a c 13 a c b a b c 8 a b a b c 15 c a b 13 c a b c a b 9 a b a c 8 a b a b c b 6 c a b 6 a c b k a b 5 b c a TABLE 1 (COM 1 '!)) 16 Fen. NAND Inputs NOR Inputs No, Expression Cct. 1 2 3 k 5 6789 Cct, 1 2 3 k 5 6 7 8 9 321 ab+bc 9 a b b c 9 a b b c 322 a(b+c)+abc 13 b c a b a c 13 b c a b a c 323 b ( a+c ) +ab Ik 12 a b b c a a c a b b 8 a b a b c 32+ ac+bc+ab 12 b c a b c 12 a b c a b 325 c+ab 5 a b c 6 a b c 326 a(b+c)+bc+abc 18 a b a c b c a b c 11 a b c a b c a b c 327 ab+ab+c 10 a b a b c 7 a b c a b c 330 ac+bc 9 b c a c 9 b c a c 331 ab+bc+bc Ik 12 b a c c a b b b c c 8 b c a b c 332 c ( a+b ) +ac ik 12 c b a a b c c c a a 8 c a b c a 333 c ( a+b ) +c ( a+b ) 15 16 c c a b b a c b a c b a 7 b c a b c a 33^ ac+b 5 c a b 6 a c b 335 b+c 1 c b k b c 336 ac+ac+b 10 c a c a b 7 b c a b c a 337 a+b+c 2 c a b 3 b c a 3+0 a(b+c) 6 b c a 5 b c a 3kL a(b+c)+abc 13 b c a b c a 13 b c a b c a 342 ab+bc 9 b c b a 9 a b c b 3^3 ab+ab+ac Ik 12 a c b b c a a a b b 8 a b a b c 3kk ac+bc 9 a c b c 9 b c a c 3^5 ac+ab+ac Ik 12 a b c c b a a a c c 8 a c a b c 3+6 b(a+c)+bc 1+ 12 b a c c a b b b c c 8 b c a b c 3^7 b(a+c)+b(a+c) 15 16 b b c a a c b a c b a c 7 a b c a b c 350 ab+ac+bc 12 b c a b c 12 b c a b c TABLE L (CONT'D) Fen, NAND Inputs NOR Inputs No. Expression Cct. 1 2 3 k 5 6 7 8 9 Cct. 1 2 3 1+56789 351 ab+ac+bc+abc 18 a b a c b c a b c 11 a b c a b c a b c 352 ab+c 5 a b c 6 a b c 353 ab+ab+c 10 a b a b c 7 c a b cab 35^ ac+b 5 a c b 6 c a b 355 ac+ac+b 10 a c a c b 7 b c a b c a 356 b+c 1 b c k b c 357 a+b+c 2 a b c 3 a b c 360 a a a 361 a+bc 5 b c a 6 b c a 362 a+bc 5 b c a 6 c b a 363 a+b 1 a b k a b 364 a+bc 5 c b a 6 b c a 365 a+c 1 a c k a c 366 a+bc+bc 10 c b b c a 7 a b c a b c 367 a+b+c 2 a b c 3 a b c 370 a+bc 5 b c a 6 b c a 371 a+bc+bc 10 b c b c a 7 a b c a b c 372 a+c 1 a c k a c 373 a+b+c 2 a b c 3 a b c 37^ a+b 1 a b h a b 375 a+b+c 2 a b c 3 a b c 376 a+b+c 2 a b c 3 a b c 377 1 1 1 5. CIRCUIT DIAGRAMS Circuit 1 Circuit 2 Circuit 3 L 2 ^L 3 i>- ^ 1 5 1 Circuit 8 Circuit 9 Circuit k 3- Circuit 5 3- Circuit 6 1 2 3 5 6 7 8 9 Circuit 10 Circuit 11 Circuit 7 3 ,5 Circuit 12 -18- 3 - k r 5 — 6 - Circuit 13 Circuit 16 Circuit Ik Circuit 17 Circuit 15 Circuit 1< 6. CONCLUSION.: The results show that nearly all of the 256 functions of three variables can be generated using four or fewer NOR or NAND elements, and that that fan-out in all circuits is one. As in Hellerman's catalog, roughly half of the NAND circuits are those which result when the minimum-OR polynomial is rewritten in terms of the NAND connective. The analogous statement holds for NOR circuits. It is speculated that this fraction will get smaller and smaller as the number of variables in the function is increased. Nevertheless, the cir- cuit obtained from the minimum-OR polynomial serves as a good starting point in the search for a simple realization. One way in which the table could be used when more variables are present would be to decompose the function and use the circuits in the table to realize the constituents. This catalog, along with the one by Hellerman, should prove useful in the design of simple circuits. However, a more useful tool would be a computer program capable of producing, in a reasonable length of time, a minimal circuit for any arbitrary function. Perhaps such a program will be available in the future . -20- BIBLIOGRAPHY 1. Earle, J., "Synthesizing Minimal Stroke and Dagger Functions," IRE Int. Conv. Record , Part 2, pp. 55-65; i960. 2. Hellerman, L., "A Catalog of Three -Variable OR- Invert and AND- Invert Logical Circuits," IEEE Trans, on Electronic Computers , Vol. EC-12, pp. 198-223; June I963. 3. Maley, G. A., and J. Earle, The Logic Design of Transistor Digital Computers , Prentice-Hall, Englewood Cliffs, N.J., Chap. 6; 1963. 4. Scott, N. R., Analog and Digital Computer Technology , McGraw-Hill, New York, pp. ^31-^38; I960. 5. Shubert, E. J., "Logical Design by Regression," Trans. AIEE , Vol, 80 (Commun. and Electronics, No. 56), pp. 380- 383; September I96I. -21- a/ JVH 2 8 1969